{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 一.CRF的定义\n",
    "条件随机场是给定随机变量$X$的条件下，随机变量$Y$的马尔科夫随机场。所以属于条件随机场的随机变量其实是$Y$，更加正式的定义如下：   \n",
    "\n",
    "设$X$与$Y$是随机变量，$P(Y\\mid X)$是在给定$X$的条件下$Y$的条件概率分布。若随机变量$Y$构成一个由无向图$G=(V,E)$表示的马尔科夫随机场，即（下面是局部马尔科夫性的定义）：   \n",
    "\n",
    "$$\n",
    "P(Y_v\\mid X,Y_w,w\\neq v)=P(Y_v\\mid X,Y_w,w\\sim v)\n",
    "$$   \n",
    "\n",
    "对任意节点$v$都成立，则称条件概率分布$P(Y\\mid X)$为条件随机场。式中$w\\sim v$表示在图$G=(V,E)$中与节点$v$有边直接相连的所有节点$w$，$w\\neq v$表示节点$v$以外的所有节点，$Y_v$为节点$v$对应的随机变量，$Y_w$为节点集合$w$对应的随机变量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二.线性链CRF的定义\n",
    "对于处理序列标注问题，使用更多的是线性链条件随机场，如下图：   \n",
    "\n",
    "![avatar](./source/12_CRF_线性链.png)  \n",
    "\n",
    "这里，$X=(X_1,X_2,...,X_n),Y=(Y_1,Y_2,...,Y_n)$均为线性链表示的随机变量序列，若在给定随机变量$X$的条件下，随机变量序列$Y$的条件概率分布$P(Y\\mid X)$构成条件随机场，即满足如下的局部马尔可夫性：   \n",
    "\n",
    "$$\n",
    "P(Y_i\\mid X,Y_1,Y_2,...,Y_{i-1},Y_{i+1},...,Y-n)=P(Y_i\\mid X,Y_{i-1},Y_{i+1}),i=1,2,..,n(在i=1或n时，只考虑单边)\n",
    "$$  \n",
    "\n",
    "则称$P(Y\\mid X)$为线性链条件随机场，在标注问题中，$X$表示输入观测序列，$Y$表示对应的输出标记序列。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 三.CRF的参数化形式  \n",
    "由上一节的内容可以知道线性链CRF的$P(Y\\mid X)$是构建在最大团$(Y_1,Y_2),(Y_2,Y_3),...,(Y_{n-1},Y_n)$之上的，那么还有一个问题就是最大团上的势函数如何定义呢？这里参考了对数线性模型的方式，即首先人工定义一系列的特征函数（指示函数），然后对其进行线性组合，最后做softmax（类比前面介绍的最大熵模型），而线性组合的各特征函数的权重便是CRF的参数，更加标准的定义如下：   \n",
    "\n",
    "设$P(Y\\mid X)$为线性链条件随机场，则在随机变量$X$取值为$x$的条件下，随机变量$Y$取值为$y$的条件概率具有如下形式：   \n",
    "\n",
    "$$\n",
    "P(y\\mid x)=\\frac{1}{Z(x)}exp(\\sum_{i,k}\\lambda_kt_k(y_{i-1},y_i,x,i)+\\sum_{i,l}\\mu_ls_l(y_i,x,i))\n",
    "$$   \n",
    "\n",
    "其中：  \n",
    "\n",
    "$$\n",
    "Z(x)=\\sum_yexp(\\sum_{i,k}\\lambda_kt_k(y_{i-1},y_i,x,i)+\\sum_{i,l}\\mu_ls_l(y_i,x,i))\n",
    "$$  \n",
    "\n",
    "这里，$t_k$是定义在边上的特征函数，称为转移特征，依赖于当前和前一个位置；$s_l$是定义在结点上的特征函数，称为状态特征，依赖于当前位置，而$\\lambda_k,\\mu_l$分为它们对应的权值，也就是CRF模型的参数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 简化形式\n",
    "上面的表达方式有些繁杂，特别是$\\sum_{i,k}$以及$\\sum_{i,l}$这两项，我们令$k=1,2,...,K_1,l=1,2,...,K_2,K=K_1+K_2$，对上面的公式做一些简化：  \n",
    "\n",
    "$$\n",
    "\\sum_{i,k}\\lambda_kt_k(y_{i-1},y_i,x,i)+\\sum_{i,l}\\mu_ls_l(y_i,x,i)\\\\\n",
    "=\\sum_{k=1}^{K_1}\\lambda_k[\\sum_it_k(y_{i-1},y_i,x,i)]+\\sum_{l=1}^{K_2}\\mu_l[\\sum_is_l(y_i,x,i)]\\\\\n",
    "=[\\lambda_1,..,\\lambda_{K_1},\\mu_1,..,\\mu_{K_2}][\\sum_it_1(y_{i-1},y_i,x,i),...,\\sum_it_{K_1}(y_{i-1},y_i,x,i),\\sum_is_1(y_i,x,i),...,\\sum_is_{K_2}(y_i,x,i)]^T\\\\\n",
    "=[w_1,..,w_K][f_1(y,x),...,f_K(y,x)]^T\\\\\n",
    "=w^TF(y,x)\n",
    "$$   \n",
    "\n",
    "其中：   \n",
    "\n",
    "$$\n",
    "w_k=\\left\\{\\begin{matrix}\n",
    "\\lambda_k & k=1,2,...,K_1\\\\ \n",
    "\\mu_l & k=K_1+l,l=1,2,...,K_2\n",
    "\\end{matrix}\\right.\\\\\n",
    "w=(w_1,w_2,...,w_K)^T\n",
    "$$   \n",
    "\n",
    "$$\n",
    "f_k(y,x)=\\left\\{\\begin{matrix}\n",
    "\\sum_it_k(y_{i-1},y_i,x,i) & k=1,2,...,K_1\\\\ \n",
    "\\sum_is_l(y_i,x,i) & k=K_1+l,l=1,2,...,K_2\n",
    "\\end{matrix}\\right.\\\\\n",
    "F(y,x)=(f_1(y,x),f_2(y,x),...,f_K(y,x))^T\n",
    "$$  \n",
    "\n",
    "所以，条件概率可以简写为：   \n",
    "\n",
    "$$\n",
    "P(y\\mid x)=\\frac{1}{Z(x)}exp\\sum_{k=1}^Kw_kf_k(y,x)\\\\\n",
    "Z(x)=\\sum_yexp\\sum_{k=1}^Kw_kf_k(y,x)\n",
    "$$   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 矩阵形式\n",
    "\n",
    "如果只用上面的简化形式(给定$w$)对于求$P_w(y\\mid x)$的分子项是OK滴，但是最麻烦的还是求分母项即：$Z_w(x)$，它可是要求所有的$y_i,i=1,2,..,n$的所有可能取值情况，假设它有$m$个状态，即$y_i\\in \\{q_1,q_2,..,q_{m}\\},i=1,2,..,n$，那么：   \n",
    "\n",
    "$$\n",
    "Z_w(x)=\\sum_{y_1=q_1}^{q_m}\\sum_{y_2=q_1}^{q_m}\\cdots\\sum_{y_n=q_1}^{q_m}exp(w^TF(y,x))\n",
    "$$  \n",
    "\n",
    "这个形式在HMM里面出现过了，时间复杂度还是指数级的$O(nm^n)$，参考HMM的处理方式，我们还是要将$w^TF(y,x)$转换成$\\sum_{i=1}^n(\\cdot)$的形式，这样才方便我们利用动态规划求解$Z_w(x)$，转换其实也很简单，上面的简化形式相当于先做$\\sum_i$再做$\\sum_k$，那我们这次交换一下次序先做$\\sum_k$再做$\\sum_i$就行哒，那么我们要先将$w^TF(y,x)$为$\\sum_i\\sum_k$的形式，然后再去掉$\\sum_k$：   \n",
    "\n",
    "$$\n",
    "w^TF(y,x)=\\sum_{k=1}^Kw_kf_k(y,x)\\\\\n",
    "=\\sum_{k=1}^Kw_k\\sum_{i=1}^nf_k(y_{i-1},y_i,x,i)\\\\\n",
    "=\\sum_{i=1}^n\\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)\\\\\n",
    "=\\sum_{i=1}^nW_i(y_{i-1},y_i\\mid x)\n",
    "$$   \n",
    "\n",
    "这里，$W_i(y_{i-1},y_i\\mid x)=\\sum_{k=1}^Kw_kf_k(y_{i-1},y_i,x,i)$，所以这时：  \n",
    "\n",
    "$$\n",
    "Z_w(x)=\\sum_{y_1=q_1}^{q_m}\\sum_{y_2=q_1}^{q_m}\\cdots\\sum_{y_n=q_1}^{q_m}exp(\\sum_{i=1}^n W_i(y_{i-1},y_i\\mid x))\\\\\n",
    "=\\sum_{y_1=q_1}^{q_m}\\sum_{y_2=q_1}^{q_m}\\cdots\\sum_{y_n=q_1}^{q_m}exp(W_1(y_0,y_1\\mid x))exp(W_2(y_1,y_2\\mid x))\\cdots exp(W_n(y_{n-1},y_n\\mid x))\n",
    "$$  \n",
    "\n",
    "到这里，可以嗅出熟悉的味道了吧，是不是和HMM中的概率计算很像了呢？将这里的$x$看做HMM中的$o$，将$y$看着HMM中的$i$，将$exp(W_1(y_0,y_1\\mid x))$看做$b_{i1}(o_1)a_{i1i2}$，那求解方式不就是一回事了，使用动态回归就可以哒，下面叙述其过程：   \n",
    "\n",
    ">（1）假设$y_i,i=1,2,..,n$共有$m$种取值$y_i\\in \\{q_1,q_2,...,q_{m}\\}$，为了计算方便，我们为$y$引进特殊的起点和终点状态标记$y_0=start$和$y_{n+1}=stop$，不妨假设$start$和$stop$对应的状态为$q_0$和$q_{m+1}$，所以，现在$y_i$的取值状态多了2种，即$m+2$种      \n",
    "\n",
    ">（2）对$i=1,2,3,...,n+1$，每一个位置构建一个$m+2$阶的矩阵：    \n",
    "$$\n",
    "M_i(x)=[M_i(q_o,q_t\\mid x)]_{(m+2)\\times(m+2)}\\\\\n",
    "o,t=0,1,2,...,m,m+1\n",
    "$$  这里，$[M_i(x)]_{o,t}=M_i(q_o,q_t\\mid x)=exp(\\sum_{k=1}^Kw_kf_k(q_o,q_t,x,i))$  \n",
    "\n",
    ">（3）所以，通过DP，我们可以求得：  \n",
    "\n",
    "$$\n",
    "P_w(y\\mid x)=\\frac{1}{Z_w(x)}\\prod_{i=1}^{n+1}M_i(y_{i-1},y_i\\mid x)\\\\\n",
    "Z_w(x)=[M_1(x)M_2(x)\\cdots M_{n+1}(x)]_{0,m+1}$$   \n",
    "\n",
    "这里，下标$0,m+1$即是对应的$start$所在行，$stop$所在列的元素，另外由于$y$在头尾新增加了一个特征状态，所以$x$也可以在头尾对应新增加一个特殊占位符"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
